/*
https://leetcode-cn.com/problems/cherry-pickup/solution/zhai-ying-tao-by-leetcode/
 */
import java.util.Arrays;

public class Solution741 {
    public int cherryPickup(int[][] grid) {
        int n=grid.length;
        int[][][] f=new int[n][n][n];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                Arrays.fill(f[i][j],Integer.MIN_VALUE);
            }
        }
        return Math.max(0,dfs(0,0,0,f,grid));
    }

    private int dfs(int a, int b, int c, int[][][] f, int[][] grid) {
        int n=grid.length;
        int d=a+b-c;
        if (a==n || b==n || c==n || d==n || grid[a][b]==-1 || grid[c][d]==-1){
            return -1;
        }
        if (a==n-1 && b==n-1){
            return grid[n-1][n-1];
        }
        if (f[a][b][c]!=Integer.MIN_VALUE){
            return f[a][b][c];
        }
        int ans=Math.max(Math.max(dfs(a+1,b,c,f,grid),dfs(a,b+1,c,f,grid)),Math.max(dfs(a+1,b,c+1,f,grid),dfs(a,b+1,c+1,f,grid)));
        if (ans<0){
            return f[a][b][c]=-1;
        }
        ans+=grid[a][b];
        if (a!=c){
            ans+=grid[c][d];
        }
        return f[a][b][c]=ans;
    }


    public static void main(String[] args) {
        System.out.println(new Solution741().cherryPickup(new int[][]{{1,1,1,1,0,0,0},{0,0,0,1,0,0,0},{0,0,0,1,0,0,1},{1,0,0,1,0,0,0},{0,0,0,1,0,0,0},{0,0,0,1,0,0,0},{0,0,0,1,1,1,1}}));
    }
}
